#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <climits>

void print(std::vector<int>& nums)
{
    for(auto& e : nums){
        std::cout << e << " ";
    }
    std::cout << std::endl;
}

void bubble_sort(std::vector<int>& nums)
{
    print(nums);

    for(int i=0; i<nums.size(); i++) { // 控制交换的元素个数
        int flag = 0;
        for(int j = 1; j<nums.size() - i; j++) {// 进行交换
            if(nums[j - 1] > nums[j]) {
                std::swap(nums[j-1], nums[j]);
                flag = 1;
            }
        }

        if(flag == 0) break;
    }
    print(nums);
}

void insert_sort(std::vector<int>& nums)
{
    print(nums);
    for(size_t i=0; i<nums.size() - 1; i++) {
        size_t end = i; // 有序部分的最后一个元素的下标
        int tmp = nums[end + 1]; // 待插入的数据

        // 待插入数据，依次与有序部分的元素进行比较
        while(end >= 0) {
            if(tmp >= nums[end]) break;
            nums[end+1] = nums[end];
            end--;
        }
        nums[end + 1] = tmp;
    }
    print(nums);
}

void shell_sort(std::vector<int>& nums)
{
    print(nums);
    size_t gap = nums.size();
    while(gap > 1) {
        gap = gap / 3 + 1;
        for(size_t i = 0; i < nums.size() - gap; i++) { // 分组，对每组进行插入排序

            size_t end = i; // 每组的开始
            int tmp = nums[end + gap]; // 待插入数据
            while(end >= 0) {
                if(tmp >= nums[end]) break;
                nums[end + gap] = nums[end];
                end -= gap;
            }
            nums[end + gap] = tmp;
        }
    }
    print(nums);
}

void select_sort1(std::vector<int>& nums)
{
    print(nums);
    for(int i=0; i<nums.size(); i++) {
        int min_index = i;
        for(int j = i + 1; j<nums.size(); j++) {
            min_index = nums[min_index] > nums[j] ? j : min_index;
        }
        std::swap(nums[i], nums[min_index]);
    }
    print(nums);
}

void select_sort2(std::vector<int>& nums)
{
    print(nums);
    int begin = 0;
    int end = nums.size() - 1;

    while(begin < end) {
        int min_index = begin;
        int max_index = end;
        for(int i = begin; i<=end; i++) {

            min_index = nums[min_index] > nums[i] ? i : min_index;
            max_index = nums[max_index] < nums[i] ? i : max_index;
        }    
        std::swap(nums[begin], nums[min_index]);
        if(max_index == begin) {
            max_index = min_index;
        }
        std::swap(nums[end], nums[max_index]);
        begin++;
        end--;
    }
    print(nums);
}

// 大堆
void adjust_down(std::vector<int>& nums, int parent, int size)
{
    int val = nums[parent];

    int child = parent * 2 + 1;
    while(child < size) {
        if(child + 1 < size && nums[child] < nums[child + 1]) {
            child += 1;
        }

        if(val >= nums[child]) break;

        nums[parent] = nums[child];
        parent = child;
        child = parent * 2 + 1;
    }

    nums[parent] = val;
}

void heap_sort(std::vector<int>& nums)
{
    print(nums);

    // 建堆
    // 倒数第一个叶子节点：size - 1
    // 倒数第一个非叶子节点是它的父亲：(size - 1 -1) / 2
    for(int i = (nums.size() - 2) / 2; i>=0; i--) {
        adjust_down(nums, i, nums.size());
    }

    // 交换堆顶和相对的最后一个数据，并进行向下调整
    int end = nums.size() - 1;
    while(end) {
        std::swap(nums[0], nums[end]);
        adjust_down(nums, 0, end);
        end--;
    }

    print(nums);
}

int getMid(std::vector<int>& nums, int left, int right)
{
    int mid = (right - left) / 2 + left;
    if(nums[left] > nums[mid]) {
        if(nums[right] > nums[left]) return left;
        else if(nums[right] < nums[mid]) return mid;
        else return right;
    }else {
        // left <= mid
        if(nums[right] > nums[mid]) return mid;
        else if(nums[right] < nums[left]) return left;
        else return right;
    }
}

void hoare_quicksort(std::vector<int>& nums, int left, int right)
{
    if(left >= right) return;

    int mid = getMid(nums, left, right);
    std::swap(nums[left], nums[mid]);

    int pivot = nums[left];
    int R = right;
    int L = left + 1;
    while(L < R) {
        // R向左走，找小
        while(R > L && nums[R] > pivot) {
            R--;
        }

        // L向右走，找大
        while(L < R && nums[L] < pivot) {
            L++;
        }

        std::swap(nums[L], nums[R]);
    }
    std::swap(nums[left], nums[R]);

    // left,R-1 R R+1 right
    hoare_quicksort(nums, left, R-1);
    hoare_quicksort(nums, R + 1, right);
}

// 三路划分，将数组分为三部分，<pivot, =pivot 和>pivot
std::pair<int, int> partition(std::vector<int>& nums, int left, int right)
{
    int mid = getMid(nums, left, right);
    std::swap(nums[mid], nums[left]);

    int pivot = nums[left];
    int lt = left;
    int rt = right;

    // [left, lt) [lt, rt] (rt, right]
    int i = left + 1;
    while(i <= rt) {
        if(nums[i] < pivot) {
            std::swap(nums[i++], nums[lt++]);
        }else if(nums[i] > pivot) {
            std::swap(nums[i], nums[rt--]);
        }else {
            i++;
        }
    }

    return {lt, rt};
}

void quick_sort(std::vector<int>& nums, int left, int right)
{
    if(left >= right) return;
    std::pair<int, int> range = partition(nums, left, right);

    // [left, lt) [lt, rt] (rt, right]
    quick_sort(nums, left, range.first - 1);
    quick_sort(nums, range.second + 1, right);
}

void quick_sort_tail_rec(std::vector<int>& nums, int left, int right)
{
    while(left < right) {
        std::pair<int, int> range = partition(nums, left, right);
        if(range.first - left < right - range.second) {
            // 左区间短
            quick_sort_tail_rec(nums, left, range.first - 1);
            left = range.second + 1;
        }else {
            quick_sort_tail_rec(nums, range.second + 1, right);
            right = range.first - 1;
        }
    }
}

void quick_sort_stack(std::vector<int>& nums, int left, int right)
{
    std::stack<std::pair<int, int>> st;
    st.push({left, right});
    while(!st.empty()) {
        auto [begin, end] = st.top();
        st.pop();

        std::pair<int, int> range = partition(nums, begin, end);
        // [begin, range.frist - 1] [range.first, range.second] [range.second + 1, end]
        // 先压右区间，再压左区间；先压右端点，再压左端点

        if(range.second + 1 < end) {
            st.push({range.second + 1, end});
        }
        if(range.first - 1 > begin) {
            st.push({begin, range.first - 1});
        }
    }
}

void quick_sort_queue(std::vector<int>& nums, int left, int right)
{
    std::queue<std::pair<int, int>> q;
    q.push({left, right});
    while(!q.empty()) {
        auto [begin, end] = q.front();
        q.pop();

        std::pair<int, int> range = partition(nums, begin, end);
        // [begin, range.frist - 1] [range.first, range.second] [range.second + 1, end]

        if(range.first - 1 > begin) {
            q.push({begin, range.first - 1});
        }
        if(range.second + 1 < end) {
            q.push({range.second + 1, end});
        }
    }
}

void _merge_sort(std::vector<int>& nums, int* tmp, int left, int right)
{
    // 区间个数为1，或者不存在时，不需要进行归并
    if(left >= right) return;

    // 1.将数组分为左右两部分，对这两部分分别进行递归
    int mid = (right - left) / 2 + left;
    // [left, mid] [mid + 1, right]
    _merge_sort(nums, tmp, left, mid);
    _merge_sort(nums, tmp, mid + 1, right);

    // 2.归并完成后，左右子区间已经有序，此时合并
    int i = left;
    int j = mid + 1;
    int k = left;
    while(i <= mid && j <= right) {
        if(nums[i] <= nums[j]) { // 相同情况下选择左子数组，保证稳定性
            tmp[k++] = nums[i++];
        }else {
            tmp[k++] = nums[j++];
        }
    }

    // 3.判断那个条件导致循环结束，将另一个子数组中的数组拷贝到辅助数组
    while(i <= mid) {
        tmp[k++] = nums[i++];
    }
    while(j <= right) {
        tmp[k++] = nums[j++];
    }

    // 4.将辅助数组中该部分内容，拷贝回原空间
    memcpy(&nums[left], tmp + left, sizeof(int)*(right - left + 1));
}

void merge_sort1(std::vector<int>& nums)
{
    // 1.开辟一个同原数组一样大的数组
    int* tmp = new int[nums.size()];

    // 2.使用子函数，对数组进行归并
    _merge_sort(nums, tmp, 0, nums.size() - 1);

    // 3.释放空间
    delete[] tmp;
}

void merge(std::vector<int>& nums, std::vector<int>& tmp, int left, int mid, int right)
{
    // 1.先将区间内容，拷贝到tmp中
    for(int i = left; i<=right; i++) {
        tmp[i] = nums[i];
    }    

    // 2.进行合并
    int i = left, j = mid + 1, k = left;
    while(i<=mid && j<=right) {
        if(tmp[i] <= tmp[j]) {
            nums[k++] = tmp[i++];
        }else {
            nums[k++] = tmp[j++];
        }
    }

    // 3.结束后，如果左区间剩余，则拷贝左区间；如果右区间剩余，则不用管，最初时已经将右区间拷贝至对应位置了
    while(i <= mid) {
        nums[k++] = tmp[i++];
    }
}

void merge_sort(std::vector<int>& nums)
{
    int n = nums.size();
    std::vector<int> tmp(n); // 辅助数组

    for(int step = 1; step < n; step *= 2) { // 每一次归并时子数组的大小
        for(int left=0; left<n; left += 2*step) { // 归并时要合并两个数组，i要跳过两个数组的大小
            int mid = left + step - 1;
            if(mid > n) break; // 区间中点大于数组个数，只有一个区间，无需合并
            int right = std::min(left + 2*step - 1, n-1); // 避免右子数组越界

            // [left, mid] [mid + 1, right]
            merge(nums, tmp, left, mid, right);
        }
    }
}

void count_sort(std::vector<int>& nums)
{
    // 1.获取数据最大和最小值，确定数据范围
    int max = INT_MIN, min = INT_MAX;
    for(auto& e : nums) {
        max = max > e ? max : e;
        min = min < e ? min : e;
    }

    // 2.创建辅助数组，统计个数
    int range = max - min + 1;
    std::vector<int> tmp(range, 0);
    for(int i=0; i<nums.size(); i++) {
        tmp[nums[i] - min]++;
    }

    // 3.还原数据
    int j = 0;
    for(int i=0; i<tmp.size(); i++) {
        while(tmp[i]--) {
            nums[j++] = i + min;
        }
    }
}

int main()
{
    std::vector<int> nums = {1,3,4,2,4,6,0,7};
    print(nums);
    //bubble_sort(nums);
    //insert_sort(nums);
    //shell_sort(nums);
    //select_sort1(nums);
    //select_sort2(nums);
    //heap_sort(nums);
    //hoare_quicksort(nums, 0, nums.size() - 1);
    //quick_sort(nums, 0, nums.size());
    //quick_sort_tail_rec(nums, 0, nums.size() - 1);
    //quick_sort_stack(nums, 0, nums.size() - 1);
    //quick_sort_queue(nums, 0, nums.size() - 1);
    //merge_sort(nums);
    count_sort(nums);
    print(nums);
    return 0;
}